package basic.study.wantOffer.chapter5;

/**
 * @author Kevin
 * @date 2020/4/26 10:51
 */
public class Problem49 {
    // 一开始的做法
    public boolean isUgly(int num) {
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return (num==1)?true:false;
    }
    public int GetUglyNumber(int index) {
        if (index <= 0) return 0;

        int number = 0;
        int uglyFound = 0;
        while (uglyFound < index) {
            number++;
            if (isUgly(number)) {
                uglyFound++;
            }
        }
        return number;
    }


    // 优化思路：创建数组，里面是已排好序的丑数，每个丑数都是前面的丑数乘以2、3、5得到的
    private static int getUgly(int n) {
        if (n < 0) return 0;

        int[] unglyArray = new int[n];
        unglyArray[0] = 1;
        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;
        for (int i = 1; i < n; i++) {
            int min = getMin(unglyArray[multiply2] * 2, unglyArray[multiply3] * 3, unglyArray[multiply5] * 5);
            unglyArray[i] = min;
            System.out.println(unglyArray[i]);
            while (unglyArray[multiply2] * 2 == unglyArray[i])
                multiply2++;
            while (unglyArray[multiply3] * 3 == unglyArray[i])
                multiply3++;
            while (unglyArray[multiply5] * 5 == unglyArray[i])
                multiply5++;
        }
        return unglyArray[n - 1];
    }
    private static int getMin(int i, int j, int k) {
        int min = (i<j) ? i : j;
        return (min<k) ? min : k;
    }

}
